//
// Created by xili on 2024/9/10 8:57.
// GO BIG OR GO HOME.
//
#include "leetcode.h"

class Solution {
public:
    int findMaximizedCapital(int k, int w, vector<int> &profits, vector<int> &capital) {
        int n = profits.size();
        vector<int> id(n);
        iota(id.begin(), id.end(), 0);
        sort(id.begin(), id.end(), [&](int i, int j) { return capital[i] < capital[j]; });
        priority_queue<int> heap;
        int i = 0;
        while (k-- > 0) {
            while (i < n && w >= capital[id[i]]) {
                heap.push(profits[id[i++]]);
            }
            if (heap.empty()) {
                break;
            }
            w += heap.top();
            heap.pop();
        }
        return w;
    }
};